AlgorithmsDynamic Prgrming

Dynamic Programming(동적계획법)

동적계획법, 알고리즘

The divide and conquer algorithm works in problems such as Mergesort, where the smaller instances are unrelated. However, in problems such as nth Fibonacci term, the smaller instances are related. For example, to compute the fifth Fibonacci term we need to compute the fourth and third Fibonacci terms. However, the determinations of the fourth and third Fibonacci terms are related in that they both require the second Fibonacci term. Because the divide-and-conquer algorithm makes these two determinations independently, it ends up computing the second Fibonacci term more than once.

분할정복법으로 피보나치 수열을 계산하면 같은 항을 여러번 계산하는 결과를 초래하므로 비효율적인 알고리즘이 된다. 분할정복법은 합병정렬과 같이 분할된 부분들 사이에 서로 상관관계가 없는 문제를 해결하는데 적합한 방식임을 기억해야 한다.

nth Fibonacci Term using Divide-and-Conquer

// nth Fibonacci Term using Divide-and-Conquer
int fib(int n)
{
    if (n <= 1)
        return n;
    else
        return fib(n-1) + fib(n-2);
}

// 5th Fibonacci Term : fib(2)를 두 번 이상 계산하는 비효율 발생
fib(5) = fib(4) + fib(3)
fib(4) = fib(3) + fib(2) // fib(4)에서도 fib(2)를 독립적으로 계산
fib(3) = fib(2) + fib(1) // fib(3)에서도 fib(2)를 독립적으로 계산
...

피보나치 수열을 동적계획법 기법으로 해결하면 훨씬 더 효율적인 계산이 가능해진다. n번째 항의 값을 구할 때 이미 구해놓은 n-1번째 항과 n-2번째 항을 이용하기 때문이다.

nth Fibonacci Term using Dynamic Programming

// nth Fibonacci Term using Dynamic Programming
int fibonacci(int n)
{
    int i;
    int f[n];
    f[0] = 0;

    if (n > 0)
    {
        f[1] = 1;
        for (i = 2; i <= n; ++i)
            f[i] = f[i-1] + f[i-2];
    }

    return f[n];
}


The Dynamic Programming Approach

Dynamic programming is similar to divide-and-conquer in that an instance of a problem is divided into smaller instances. However, in this approach we solve small instances first, store the results, and later, whenever we need a result, look it up instead of recomputing it. The terms dynamic programming comes from control theory, and in this sense programming means the use of an array (table) in which a solution is constructed.

  1. Establish a recursive property that gives the solution to an instance of the problem.

  2. Solve an instance of the problem in a bottom-up fashion by solving smaller instances first.

  3. Dynamic programming is a bottom-up approach.

동적계획법은 원래의 문제를 더 작은 문제로 분할한다는 점에서 분할정복법과 유사하다. 이 기법은 bottom-up 방식으로, 먼저 작은 문제들을 풀어 그 결과를 저장하고 나중에 결과가 필요할 때마다 값을 재계산하지 않고 찾아보며 최종 해에 도달하게 된다. 분할정복법의 top-down 방식과는 정반대되는 개념이다.

“동적계획법(동적프로그래밍)”이라는 용어는 제어 이론에서 나온다. 여기서 “프로그래밍”은 솔루션이 구성되는 배열(테이블)의 사용을 의미한다.

Share